﻿using System.Collections;
using System.Collections.Generic;
using System;
using System.Diagnostics;
using System.Runtime.Serialization;

namespace Test
{


    //
    // A binary search tree is a red-black tree if it satifies the following red-black properties: 
    // 1. Every node is either red or black 
    // 2. Every leaf (nil node) is black
    // 3. If a node is red, the both its children are black 
    // 4. Every simple path from a node to a descendant leaf contains the same number of black nodes
    //
    // The basic idea of red-black tree is to represent 2-3-4 trees as standard BSTs but to add one extra bit of information
    // per node to encode 3-nodes and 4-nodes. 
    // 4-nodes will be represented as:          B
    //                                                              R            R 
    // 3 -node will be represented as:           B             or         B 
    //                                                              R          B               B       R
    // 
    // For a detailed description of the algorithm, take a look at "Algorithm" by Rebert Sedgewick.
    //

    internal delegate bool TreeWalkAction<T>(TreeSet<T>.Node node);

    internal enum TreeRotation
    {
        LeftRotation = 1,
        RightRotation = 2,
        RightLeftRotation = 3,
        LeftRightRotation = 4,
    }

    [Serializable]
    internal class TreeSet<T> : ICollection<T>, ICollection, ISerializable, IDeserializationCallback
    {
        Node _root;
        IComparer<T> _comparer;
        int _count;
        int _version;
        private Object _syncRoot;

        private const String ComparerName = "Comparer";
        private const String CountName = "Count";
        private const String ItemsName = "Items";
        private const String VersionName = "Version";

        private SerializationInfo _siInfo; //A temporary variable which we need during deserialization.

        public TreeSet(IComparer<T> comparer)
        {
            _comparer = comparer ?? Comparer<T>.Default;
        }

        protected TreeSet(SerializationInfo info, StreamingContext context)
        {
            _siInfo = info;
        }


        public int Count { get { return _count; } }
        public IComparer<T> Comparer { get { return _comparer; } }
        bool ICollection<T>.IsReadOnly { get { return false; } }
        bool ICollection.IsSynchronized { get { return false; } }
        object ICollection.SyncRoot
        {
            get
            {
                if (_syncRoot == null)
                {
                    System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null);
                }
                return _syncRoot;
            }
        }

        public void Add(T item)
        {
            if (_root == null)
            {   // empty tree 
                _root = new Node(item, false);
                _count = 1;
                return;
            }

            //
            // Search for a node at bottom to insert the new node.
            // If we can guanratee the node we found is not a 4-node, it would be easy to do insertion.
            // We split 4-nodes along the search path. 
            //
            var current = _root;
            Node parent = null;
            Node grandParent = null;
            Node greatGrandParent = null;

            var order = 0;
            while (current != null)
            {
                order = _comparer.Compare(item, current.Item);
                if (order == 0)
                {
                    // We could have changed root node to red during the search process. 
                    // We need to set it to black before we return. 
                    _root.IsRed = false;
                    throw new Exception("is duplicate item");
                    //ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
                }

                // split a 4-node into two 2-nodes
                if (Is4Node(current))
                {
                    Split4Node(current);
                    // We could have introduced two consecutive red nodes after split. Fix that by rotation. 
                    if (IsRed(parent))
                    {
                        InsertionBalance(current, ref parent, grandParent, greatGrandParent);
                    }
                }
                greatGrandParent = grandParent;
                grandParent = parent;
                parent = current;
                current = (order < 0) ? current.Left : current.Right;
            }

            Debug.Assert(parent != null, "Parent node cannot be null here!");
            // ready to insert the new node 
            var node = new Node(item);
            if (order > 0)
            {
                parent.Right = node;
            }
            else
            {
                parent.Left = node;
            }

            // the new node will be red, so we will need to adjust the colors if parent node is also red
            if (parent.IsRed)
            {
                InsertionBalance(node, ref parent, grandParent, greatGrandParent);
            }

            // Root node is always black 
            _root.IsRed = false;
            ++_count;
            ++_version;
        }

        public void Clear()
        {
            _root = null;
            _count = 0;
            ++_version;
        }

        public bool Contains(T item)
        {
            return FindNode(item) != null;
        }

        //
        // Do a in order walk on tree and calls the delegate for each node.
        // If the action delegate returns false, stop the walk. 
        //
        // Return true if the entire tree has been walked. 
        // Otherwise returns false. 
        //
        internal bool InOrderTreeWalk(TreeWalkAction<T> action)
        {
            if (_root == null)
            {
                return true;
            }

            // The maximum height of a red-black tree is 2*lg(n+1).
            // See page 264 of "Introduction to algorithms" by Thomas H. Cormen 
            var stack = new Stack<Node>(2 * (int)Math.Log(Count + 1));
            var current = _root;
            while (current != null)
            {
                stack.Push(current);
                current = current.Left;
            }

            while (stack.Count != 0)
            {
                current = stack.Pop();
                if (!action(current))
                {
                    return false;
                }

                var node = current.Right;
                while (node != null)
                {
                    stack.Push(node);
                    node = node.Left;
                }
            }
            return true;
        }

        public void CopyTo(T[] array, int index)
        {
            if (array == null) throw new ArgumentNullException("array");
            if (index < 0) throw new ArgumentOutOfRangeException("index");
            if (array.Length - index < Count) throw new ArgumentException("array plus offset too small");
            InOrderTreeWalk(delegate(Node node) { array[index++] = node.Item; return true; });
        }

        void ICollection.CopyTo(Array array, int index)
        {
            if (array == null) throw new ArgumentNullException("array");
            if (array.Rank != 1) throw new ArgumentException("rank multi dim not supported");
            if (array.GetLowerBound(0) != 0) throw new ArgumentException("Non zera lower bound");
            if (index < 0) throw new ArgumentOutOfRangeException("index");
            if (array.Length - index < Count) throw new ArgumentException("array plus offset to small");
            var tarray = array as T[];
            if (tarray != null)
            {
                CopyTo(tarray, index);
            }
            else
            {
                var objects = array as object[];
                if (objects == null) throw new ArgumentException("invalid array type");
                try
                {
                    InOrderTreeWalk(delegate(Node node) { objects[index++] = node.Item; return true; });
                }
                catch (ArrayTypeMismatchException)
                {
                    throw new ArgumentException("invalid array type");
                }
            }
        }

        public Enumerator GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        internal Node FindNode(T item)
        {
            var current = _root;
            while (current != null)
            {
                var order = _comparer.Compare(item, current.Item);
                if (order == 0) return current;
                current = (order < 0) ? current.Left : current.Right;
            }

            return null;
        }

        public bool Remove(T item)
        {
            if (_root == null)
            {
                return false;
            }

            // Search for a node and then find its succesor.
            // Then copy the item from the succesor to the matching node and delete the successor. 
            // If a node doesn't have a successor, we can replace it with its left child (if not empty.)
            // or delete the matching node.
            //
            // In top-down implementation, it is important to make sure the node to be deleted is not a 2-node. 
            // Following code will make sure the node on the path is not a 2 Node.
            // 
            var current = _root;
            Node parent = null;
            Node grandParent = null;
            Node match = null;
            Node parentOfMatch = null;
            var foundMatch = false;
            while (current != null)
            {
                if (Is2Node(current))
                { // fix up 2-Node
                    if (parent == null)
                    {   // current is root. Mark it as red 
                        current.IsRed = true;
                    }
                    else
                    {
                        var sibling = GetSibling(current, parent);
                        if (sibling.IsRed)
                        {
                            // If parent is a 3-node, flip the orientation of the red link.
                            // We can acheive this by a single rotation
                            // This case is converted to one of other cased below. 
                            Debug.Assert(!parent.IsRed, "parent must be a black node!");
                            if (parent.Right == sibling)
                            {
                                RotateLeft(parent);
                            }
                            else
                            {
                                RotateRight(parent);
                            }

                            parent.IsRed = true;
                            sibling.IsRed = false;    // parent's color 
                            // sibling becomes child of grandParent or root after rotation. Update link from grandParent or root
                            ReplaceChildOfNodeOrRoot(grandParent, parent, sibling);
                            // sibling will become grandParent of current node 
                            grandParent = sibling;
                            if (parent == match)
                            {
                                parentOfMatch = sibling;
                            }

                            // update sibling, this is necessary for following processing 
                            sibling = (parent.Left == current) ? parent.Right : parent.Left;
                        }
                        Debug.Assert(sibling != null || sibling.IsRed == false, "sibling must not be null and it must be black!");

                        if (Is2Node(sibling))
                        {
                            Merge2Nodes(parent, current, sibling);
                        }
                        else
                        {
                            // current is a 2-node and sibling is either a 3-node or a 4-node.
                            // We can change the color of current to red by some rotation. 
                            TreeRotation rotation = RotationNeeded(parent, current, sibling);
                            Node newGrandParent = null;
                            switch (rotation)
                            {
                                case TreeRotation.RightRotation:
                                    Debug.Assert(parent.Left == sibling, "sibling must be left child of parent!");
                                    Debug.Assert(sibling.Left.IsRed, "Left child of sibling must be red!");
                                    sibling.Left.IsRed = false;
                                    newGrandParent = RotateRight(parent);
                                    break;
                                case TreeRotation.LeftRotation:
                                    Debug.Assert(parent.Right == sibling, "sibling must be left child of parent!");
                                    Debug.Assert(sibling.Right.IsRed, "Right child of sibling must be red!");
                                    sibling.Right.IsRed = false;
                                    newGrandParent = RotateLeft(parent);
                                    break;

                                case TreeRotation.RightLeftRotation:
                                    Debug.Assert(parent.Right == sibling, "sibling must be left child of parent!");
                                    Debug.Assert(sibling.Left.IsRed, "Left child of sibling must be red!");
                                    newGrandParent = RotateRightLeft(parent);
                                    break;

                                case TreeRotation.LeftRightRotation:
                                    Debug.Assert(parent.Left == sibling, "sibling must be left child of parent!");
                                    Debug.Assert(sibling.Right.IsRed, "Right child of sibling must be red!");
                                    newGrandParent = RotateLeftRight(parent);
                                    break;
                            }

                            newGrandParent.IsRed = parent.IsRed;
                            parent.IsRed = false;
                            current.IsRed = true;
                            ReplaceChildOfNodeOrRoot(grandParent, parent, newGrandParent);
                            if (parent == match)
                            {
                                parentOfMatch = newGrandParent;
                            }
                            grandParent = newGrandParent;
                        }
                    }
                }

                // we don't need to compare any more once we found the match
                int order = foundMatch ? -1 : _comparer.Compare(item, current.Item);
                if (order == 0)
                {
                    // save the matching node 
                    foundMatch = true;
                    match = current;
                    parentOfMatch = parent;
                }

                grandParent = parent;
                parent = current;

                if (order < 0)
                {
                    current = current.Left;
                }
                else
                {
                    current = current.Right;       // continue the search in  right sub tree after we find a match 
                }
            }

            // move successor to the matching node position and replace links
            if (match != null)
            {
                ReplaceNode(match, parentOfMatch, parent, grandParent);
                --_count;
            }

            if (_root != null)
            {
                _root.IsRed = false;
            }
            ++_version;
            return foundMatch;
        }

        // LinkDemand here is unnecessary as this is a methodimpl and linkdemand from the interface should suffice 
        void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
        {
            GetObjectData(info, context);
        }

        protected void GetObjectData(SerializationInfo info, StreamingContext context)
        {
            if (info == null) throw new ArgumentNullException("info");

            info.AddValue(CountName, _count); //This is the length of the bucket array. 
            info.AddValue(ComparerName, _comparer, typeof(IComparer<T>));
            info.AddValue(VersionName, _version);

            if (_root == null) return;
            var items = new T[Count];
            CopyTo(items, 0);
            info.AddValue(ItemsName, items, typeof(T[]));
        }

        void IDeserializationCallback.OnDeserialization(Object sender)
        {
            OnDeserialization(sender);
        }

        protected void OnDeserialization(Object sender)
        {
            if (_comparer != null)
            {
                return; //Somebody had a dependency on this class and fixed us up before the ObjectManager got to it. 
            }

            if (_siInfo == null)
            {
                throw new SerializationException();
            }

            _comparer = (IComparer<T>)_siInfo.GetValue(ComparerName, typeof(IComparer<T>));
            var savedCount = _siInfo.GetInt32(CountName);

            if (savedCount != 0)
            {
                var items = (T[])_siInfo.GetValue(ItemsName, typeof(T[]));

                if (items == null)
                {
                    throw new SerializationException("missing values");
                }

                for (var i = 0; i < items.Length; i++)
                {
                    Add(items[i]);
                }
            }

            _version = _siInfo.GetInt32(VersionName);
            if (_count != savedCount)
            {
                throw new SerializationException("mismatched count");
            }
            _siInfo = null;
        }

        private static Node GetSibling(Node node, Node parent)
        {
            return parent.Left == node ? parent.Right : parent.Left;
        }

        // After calling InsertionBalance, we need to make sure current and parent up-to-date. 
        // It doesn't matter if we keep grandParent and greatGrantParent up-to-date 
        // because we won't need to split again in the next node.
        // By the time we need to split again, everything will be correctly set. 
        //
        private void InsertionBalance(Node current, ref Node parent, Node grandParent, Node greatGrandParent)
        {
            Debug.Assert(grandParent != null, "Grand parent cannot be null here!");
            var parentIsOnRight = (grandParent.Right == parent);
            var currentIsOnRight = (parent.Right == current);

            Node newChildOfGreatGrandParent;
            if (parentIsOnRight == currentIsOnRight)
            { // same orientation, single rotation
                newChildOfGreatGrandParent = currentIsOnRight ? RotateLeft(grandParent) : RotateRight(grandParent);
            }
            else
            {  // different orientaton, double rotation
                newChildOfGreatGrandParent = currentIsOnRight ? RotateLeftRight(grandParent) : RotateRightLeft(grandParent);
                // current node now becomes the child of greatgrandparent
                parent = greatGrandParent;
            }
            // grand parent will become a child of either parent of current. 
            grandParent.IsRed = true;
            newChildOfGreatGrandParent.IsRed = false;

            ReplaceChildOfNodeOrRoot(greatGrandParent, grandParent, newChildOfGreatGrandParent);
        }

        private static bool Is2Node(Node node)
        {
            Debug.Assert(node != null, "node cannot be null!");
            return IsBlack(node) && IsNullOrBlack(node.Left) && IsNullOrBlack(node.Right);
        }

        private static bool Is4Node(Node node)
        {
            return IsRed(node.Left) && IsRed(node.Right);
        }

        private static bool IsBlack(Node node)
        {
            return (node != null && !node.IsRed);
        }

        private static bool IsNullOrBlack(Node node)
        {
            return (node == null || !node.IsRed);
        }

        private static bool IsRed(Node node)
        {
            return (node != null && node.IsRed);
        }

        private static void Merge2Nodes(Node parent, Node child1, Node child2)
        {
            Debug.Assert(IsRed(parent), "parent must be be red");
            // combing two 2-nodes into a 4-node 
            parent.IsRed = false;
            child1.IsRed = true;
            child2.IsRed = true;
        }

        // Replace the child of a parent node. 
        // If the parent node is null, replace the root. 
        private void ReplaceChildOfNodeOrRoot(Node parent, Node child, Node newChild)
        {
            if (parent != null)
            {
                if (parent.Left == child)
                {
                    parent.Left = newChild;
                }
                else
                {
                    parent.Right = newChild;
                }
            }
            else
            {
                _root = newChild;
            }
        }

        // Replace the matching node with its succesor.
        private void ReplaceNode(Node match, Node parentOfMatch, Node succesor, Node parentOfSuccesor)
        {
            if (succesor == match)
            {  // this node has no successor, should only happen if right child of matching node is null. 
                Debug.Assert(match.Right == null, "Right child must be null!");
                succesor = match.Left;
            }
            else
            {
                Debug.Assert(parentOfSuccesor != null, "parent of successor cannot be null!");
                Debug.Assert(succesor.Left == null, "Left child of succesor must be null!");
                Debug.Assert((succesor.Right == null && succesor.IsRed) || (succesor.Right.IsRed && !succesor.IsRed), "Succesor must be in valid state");
                if (succesor.Right != null)
                {
                    succesor.Right.IsRed = false;
                }

                if (parentOfSuccesor != match)
                {   // detach succesor from its parent and set its right child 
                    parentOfSuccesor.Left = succesor.Right;
                    succesor.Right = match.Right;
                }

                succesor.Left = match.Left;
            }

            if (succesor != null)
            {
                succesor.IsRed = match.IsRed;
            }

            ReplaceChildOfNodeOrRoot(parentOfMatch, match, succesor);
        }

        internal void UpdateVersion()
        {
            ++_version;
        }

        private static Node RotateLeft(Node node)
        {
            var x = node.Right;
            node.Right = x.Left;
            x.Left = node;
            return x;
        }

        private static Node RotateLeftRight(Node node)
        {
            var child = node.Left;
            var grandChild = child.Right;

            node.Left = grandChild.Right;
            grandChild.Right = node;
            child.Right = grandChild.Left;
            grandChild.Left = child;
            return grandChild;
        }

        private static Node RotateRight(Node node)
        {
            var x = node.Left;
            node.Left = x.Right;
            x.Right = node;
            return x;
        }

        private static Node RotateRightLeft(Node node)
        {
            var child = node.Right;
            var grandChild = child.Left;

            node.Right = grandChild.Left;
            grandChild.Left = node;
            child.Left = grandChild.Right;
            grandChild.Right = child;
            return grandChild;
        }

        private static TreeRotation RotationNeeded(Node parent, Node current, Node sibling)
        {
            Debug.Assert(IsRed(sibling.Left) || IsRed(sibling.Right), "sibling must have at least one red child");
            if (IsRed(sibling.Left))
            {
                return parent.Left == current ? TreeRotation.RightLeftRotation : TreeRotation.RightRotation;
            }
            return parent.Left == current ? TreeRotation.LeftRotation : TreeRotation.LeftRightRotation;
        }

        private static void Split4Node(Node node)
        {
            node.IsRed = true;
            node.Left.IsRed = false;
            node.Right.IsRed = false;
        }

        internal class Node
        {
            public Node(T item)
            {
                // The default color will be red, we never need to create a black node directly.
                Item = item;
                IsRed = true;
            }

            public Node(T item, bool isRed)
            {
                // The default color will be red, we never need to create a black node directly.
                Item = item;
                IsRed = isRed;
            }

            public T Item { get; set; }

            public Node Left { get; set; }

            public Node Right { get; set; }

            public bool IsRed { get; set; }
        }

        public struct Enumerator : IEnumerator<T>, IEnumerator
        {
            private readonly TreeSet<T> _tree;
            private readonly int version;
            private readonly Stack<TreeSet<T>.Node> _stack;
            private Node _current;
            static Node _dummyNode = new Node(default(T));

            private const string TreeName = "Tree";
            private const string NodeValueName = "Item";
            private const string EnumStartName = "EnumStarted";
            private const string VersionName = "Version";


            internal Enumerator(TreeSet<T> set)
            {
                _tree = set;
                version = _tree._version;

                // 2lg(n + 1) is the maximum height
                _stack = new Stack<TreeSet<T>.Node>(2 * (int)Math.Log(set.Count + 1));
                _current = null;
                Intialize();
            }

            private void Intialize()
            {
                _current = null;
                var node = _tree._root;
                while (node != null)
                {
                    _stack.Push(node);
                    node = node.Left;
                }
            }

            public bool MoveNext()
            {
                if (version != _tree._version)
                {
                    //ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
                    throw new Exception("Invalid version");
                }

                if (_stack.Count == 0)
                {
                    _current = null;
                    return false;
                }

                _current = _stack.Pop();
                var node = _current.Right;
                while (node != null)
                {
                    _stack.Push(node);
                    node = node.Left;
                }
                return true;
            }

            public void Dispose()
            {
            }

            public T Current
            {
                get
                {
                    return _current != null ? _current.Item : default(T);
                }
            }

            object IEnumerator.Current
            {
                get
                {
                    if (_current != null)
                        return _current.Item;

                    //ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
                    throw new Exception("Invalid operation");
                }
            }

            internal bool NotStartedOrEnded
            {
                get
                {
                    return _current == null;
                }
            }

            internal void Reset()
            {
                if (version != _tree._version)
                {
                    //ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
                    throw new Exception("Invalid version");
                }

                _stack.Clear();
                Intialize();
            }

            void IEnumerator.Reset()
            {
                Reset();
            }
        }
    }
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.
